Graph / Steiner tree (Bibtex)

P263: Enumeration of all Steiner $W$-trees in a connected graph

Input:

A connected graph $G = (V, E)$, a vertex set $W \subseteq V$ such that $|W| = k$, for a fixed integer $k$.

Output:

Enumeration of all Steiner $W$-trees in $G$.

Complexity:

$O(|V|^2(|V|+|E|) + |V|^{k-2} + N|V|)$ total time with $O(|V|^{k-2} + |V|^2(|V| + |E|))$ space.

Comment:

A connected subgraph $T$ of $G$ is a Steiner $W$-tree if $W \subseteq V(T)$ and $|E(T)$ is minimum.

Reference:

[Dourado2014] (Bibtex)